from typing import List


class Solution:
    """
    面试经典150题-[数组/字符串]-88. 合并两个有序数组
    给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

    请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

    注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。
    为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
    """

    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
         Do not return anything, modify nums1 in-place instead.
         """
        i = m - 1
        j = n - 1
        k = m + n - 1
        while i >= 0 and j >= 0:
            if nums1[i] > nums2[j]:
                nums1[k] = nums1[i]
                i -= 1
            else:
                nums1[k] = nums2[j]
                j -= 1
            k -= 1
        while j >= 0:
            nums1[k] = nums2[j]
            j -= 1
            k -= 1

    def merge_20250724(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        :param nums1:
        :param m:
        :param nums2:
        :param n:
        :return:

        """
        k = m + n - 1
        i = m - 1
        j = n - 1
        while i >= 0 and j >= 0:
            if nums1[i] > nums2[j]:
                nums1[k] = nums1[i]
                i -= 1
            else:
                nums1[k] = nums2[j]
                j -= 1
            k -= 1
        while j >= 0:
            nums1[k] = nums2[j]
            j -= 1
            k -= 1

    def merge_review_20250724(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        解题思路：双指针分别控制两个数组的遍历
        ！！！注意原数组是非递减的
        """
        # ！！！错误，正序处理，会覆盖没有处理的子元素，需要倒序处理
        # k = 0
        # i = 0
        # j = 0
        # while i < m and j < n:
        #     if nums1[i] < nums2[j]:
        #         nums1[k] = nums1[i]
        #         i += 1
        #     else:
        #         nums1[k] = nums2[j]
        #         j += 1
        #     k += 1
        # while j < n:
        #     nums1[k] = nums2[j]
        #     j += 1
        #     k += 1

        k = m + n - 1
        i = m - 1
        j = n - 1
        while i >= 0 and j >= 0:
            if nums1[i] > nums2[j]:
                nums1[k] = nums1[i]
                i -= 1
            else:
                nums1[k] = nums2[j]
                j -= 1
            k -= 1
        while j >= 0:
            nums1[k] = nums2[j]
            j -= 1
            k -= 1


if __name__ == '__main__':
    tests_param_list = [
        {'nums1': [1, 2, 3, 0, 0, 0], 'm': 3, 'nums2': [2, 5, 6], 'n': 3},
        {'nums1': [1], 'm': 1, 'nums2': [], 'n': 0},
        {'nums1': [0], 'm': 0, 'nums2': [1], 'n': 1},
        {'nums1': [1, 2, 3, 0, 0, 0], 'm': 3, 'nums2': [1, 2], 'n': 2},
        {'nums1': [1, 0, 0], 'm': 1, 'nums2': [2, 3], 'n': 2},
    ]
    s = Solution()
    for param_dict in tests_param_list:
        print(param_dict)
        nums1 = param_dict['nums1']
        m = param_dict['m']
        nums2 = param_dict['nums2']
        n = param_dict['n']
        # s.merge(nums1, m, nums2, n)
        s.merge_review_20250724(nums1, m, nums2, n)
        print(nums1)
